1. Field of the Invention
The invention relates to systems and methods for efficiently effecting utilization of a memory having 2.sup.N addressable locations by a processor having fewer than N address outputs and to systems and methods for avoiding memory storage problems which result from inadequately regulated memory contention by multiple user programs.
2. Description of the Prior Art
A problem common to many processors is that they are capable of generating only a finite number of address bits for addressing memory, hereinafter frequently referred to as "real memory". For example, a 16 bit processor is capable of addressing only 65,536 words of memory. However, it is highly desirable that a processor be able to address "extended memories" having much larger numbers of words, especially in systems in which a plurality of user programs are stored and executed on a time-sharing basis. A common technique for accomplishing this result is to utilize address translators. Address translators are special memory devices which contain extended page addresses of real memory locations. Part of an address generated by the processor (hereinafter referred to as a "logical address") is utilized to fetch such an extended page address from the address translator. The extended page address is combined with a second part of the logical address to produce an extended address having enough address bits to address each word of the entire real memory. Execution of a user program typically involves three separate types of memory activities, referred to as program execution, input/output execution, and operating system execution. If a system utilizes only a single address translation memory, that address translation memory must be subdivided into three sections, each corresponding to a respective one of the three memory activities. The logical address utilized for execution of the operation system program and the input/output routines require utilization of an unduly large proportion of the logical address which the processor is capable of producing, thereby limiting the amount of logical address space available for execution of each user program. (The foregoing approach to extended memory operation is shown in U.S. Pat. No. 4,042,911). Alternatively, the number of logical addresses available for execution of user programs can be increased by adding additional address translators for execution of input/output routines and operating system routines. However, this approach is unduly costly.
A "memory shortage" problem frequently occurs in computing systems which execute a number of user programs on a time-shared basis. The "memory shortage" problem is a consequence of unregulated memory contention among the various time-shared user programs. The memory shortage problem arises when a number of user programs are loaded into the computing system without regard for the maximum memory requirements of each such user program. A deadlock condition can arise when a particular user program occupies a particular amount of the real memory, and is refused an additional amount of memory (needed to complete execution of the particular user program) by a "memory manager routine" because a block of memory sufficiently large to allow the execution of the present user process is unavailable. Such a deadlock condition often can be relieved only by terminating execution of one or more user programs (which have been loaded into the computing system and are being executed on a time-shared basis). This may occur at arbitrary times, and the possibility of loss of data at such times is high. The foregoing problem is further aggravated because a particular user program may run to completion on one occasion but fail on another occasion due to differences in the "mixes" of various user programs which can be executed on a time-shared basis. Often, when a particular user program's request for additional memory is rejected there is enough total free memory space to satisfy the request, but the available memory is not contiguous. As memory utilization increases above 80%, this type of situation (referred to as "fragmentation") increases dramatically. The "software burden" of a computing system is substantially increased if the operating system includes the capability of collecting fragmented portions of free memory to make them available to a requesting user program. There is an unmet need for a computing system which is capable of optimally utilizing expanded memory with a minimum amount of both hardware and software.
Accordingly, it is an object of the invention to provide an improved system and method for accessing an expanded memory system utilizing an optimum mix of hardware and software.
Another object of the invention is to provide an expanded memory system and method which avoid memory shortage problems caused by unregulated memory contention among user programs.
A further object of the invention is to provide an expanded memory system which provides maximum logical address space for each user process executed with a minimum amount of address translation memory.
Another object of the invention is to provide an expanded memory system and method which ensure that each user program loaded into the system can be executed to completion without likelihood of a shortage of memory interrupting or terminating the execution of that user program.